package test;

/**
 * 无重复最长子串
 * dp[i-1]=max(dp[i-1]+1,字符i在dp[i-1]子串中出现重复位置后的子串+str[i]的长度)
 * https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/
 */
public class WuChongFuZuiChangZiChuan {

    public static int lengthOfLongestSubstring(String s) {
        if (s.equals("")) return 0;
        int[] dp = new int[s.length()]; //记录以字符i结尾的无重复子串最大长度
        int[] startIndex  = new int[s.length()];
        dp[0] = 1;
        startIndex[0] = 0;
        int maxLen = 1;
        for (int i = 1; i < s.length(); i++) {
            String curSubStr = s.substring(i,i+1);  //当前字符
            String preSubStr = s.substring(startIndex[i-1],i); // dp[i-1]对应的子串
            if (!preSubStr.contains(curSubStr)) {
                dp[i] = dp[i-1] + 1;
                startIndex[i] = startIndex[i-1];
            }
            else {
                int index = preSubStr.indexOf(curSubStr) + startIndex[i-1]; //原串中的实际位置
                dp[i] = i - index;
                startIndex[i] = index + 1;
            }
            if (dp[i] > maxLen) maxLen = dp[i];
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("dvdf"));

    }
}
